package MiddlePractice;

import org.junit.Test;

public class Demo63 {
	
//	63. 不同路径 II
//	一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
//
//	机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
//
//	现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
	
	
	//2.内存占用的优化
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		
		int m = obstacleGrid.length, n = obstacleGrid[0].length;
		int	[] dp = new int[n];
		int ans = 1;
		int temp = 0;
		
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(obstacleGrid[i][j] == 1) {
					ans = 0;
					temp = 0;
					dp[j] = 0;
					continue;
				}
				if(i-1 >= 0) {
					ans += dp[j];
				}
				if(j-1 >= 0) {
					ans += temp;
				}
				temp = ans;
				dp[j] = ans;
				ans = 0;
			}
		}
		return dp[n-1];

    }
	
	@Test
	public void test_63() {
		int[][] test = {{0,0,0,0},{0,1,0,0},{0,0,0,0}};
		System.out.println(uniquePathsWithObstacles(test));
	}
}
